package leetcodecompetition.S105;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: Siantar
 * @Date: 2023-05-27-23:41
 * @Description: 1.0
 */
public class T6464 {
    public boolean canTraverseAllPairs(int[] nums) {
        int n = nums.length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        long sum = nums[0];
        boolean b = true;
        while (!list.isEmpty() && b) {
            int size = list.size();
            b = false;
            for (int i = 0; i < size; i++) {
                int index = list.get(i);
                int num = nums[index];
                long c = gcd(sum, num);
                if (c != 1) {
                    sum = sum * num / c;
                    list.remove(i);
                    size--;
                    b = true;
                }
            }
        }
        return true;
    }

    long gcd(long m, long n) {
        long r = 0;
        do {
            r = m % n;
            m = n;
            n = r;

        } while (r > 0);
        return m;
    }

    @Test
    public void test() {
        System.out.println(gcd(9, 8));
    }
}
